home *** CD-ROM | disk | FTP | other *** search
/ Revista CD Expert 8 / Revista CD Expert nº 08 CD1.iso / Utilitarios / Programacao / Bloodshed Dev-C++ 2.0 / _SETUP.1 / stl_bvector.h < prev    next >
C/C++ Source or Header  |  1998-03-08  |  18KB  |  617 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996,1997
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31. #ifndef __SGI_STL_INTERNAL_BVECTOR_H
  32. #define __SGI_STL_INTERNAL_BVECTOR_H
  33.  
  34. __STL_BEGIN_NAMESPACE 
  35.  
  36. static const int __WORD_BIT = int(CHAR_BIT*sizeof(unsigned int));
  37.  
  38. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  39. #pragma set woff 1174
  40. #endif
  41.  
  42. struct __bit_reference {
  43.   unsigned int* p;
  44.   unsigned int mask;
  45.   __bit_reference(unsigned int* x, unsigned int y) : p(x), mask(y) {}
  46.  
  47. public:
  48.   __bit_reference() : p(0), mask(0) {}
  49.   operator bool() const { return !(!(*p & mask)); }
  50.   __bit_reference& operator=(bool x) {
  51.     if (x)      
  52.       *p |= mask;
  53.     else 
  54.       *p &= ~mask;
  55.     return *this;
  56.   }
  57.   __bit_reference& operator=(const __bit_reference& x) { return *this = bool(x); }
  58.   bool operator==(const __bit_reference& x) const {
  59.     return bool(*this) == bool(x);
  60.   }
  61.   bool operator<(const __bit_reference& x) const {
  62.     return bool(*this) < bool(x);
  63.   }
  64.   void flip() { *p ^= mask; }
  65. };
  66.  
  67. inline void swap(__bit_reference x, __bit_reference y) {
  68.   bool tmp = x;
  69.   x = y;
  70.   y = tmp;
  71. }
  72.  
  73. struct __bit_iterator : public random_access_iterator<bool, ptrdiff_t> {
  74.   typedef __bit_reference  reference;
  75.   typedef __bit_reference* pointer;
  76.   typedef __bit_iterator iterator;
  77.  
  78.   unsigned int* p;
  79.   unsigned int offset;
  80.   void bump_up() {
  81.     if (offset++ == __WORD_BIT - 1) {
  82.       offset = 0;
  83.       ++p;
  84.     }
  85.   }
  86.   void bump_down() {
  87.     if (offset-- == 0) {
  88.       offset = __WORD_BIT - 1;
  89.       --p;
  90.     }
  91.   }
  92.  
  93.   __bit_iterator() : p(0), offset(0) {}
  94.   __bit_iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
  95.   reference operator*() const { return reference(p, 1U << offset); }
  96.   iterator& operator++() {
  97.     bump_up();
  98.     return *this;
  99.   }
  100.   iterator operator++(int) {
  101.     iterator tmp = *this;
  102.     bump_up();
  103.     return tmp;
  104.   }
  105.   iterator& operator--() {
  106.     bump_down();
  107.     return *this;
  108.   }
  109.   iterator operator--(int) {
  110.     iterator tmp = *this;
  111.     bump_down();
  112.     return tmp;
  113.   }
  114.   iterator& operator+=(difference_type i) {
  115.     difference_type n = i + offset;
  116.     p += n / __WORD_BIT;
  117.     n = n % __WORD_BIT;
  118.     if (n < 0) {
  119.       offset = (unsigned int) n + __WORD_BIT;
  120.       --p;
  121.     } else
  122.       offset = (unsigned int) n;
  123.     return *this;
  124.   }
  125.   iterator& operator-=(difference_type i) {
  126.     *this += -i;
  127.     return *this;
  128.   }
  129.   iterator operator+(difference_type i) const {
  130.     iterator tmp = *this;
  131.     return tmp += i;
  132.   }
  133.   iterator operator-(difference_type i) const {
  134.     iterator tmp = *this;
  135.     return tmp -= i;
  136.   }
  137.   difference_type operator-(iterator x) const {
  138.     return __WORD_BIT * (p - x.p) + offset - x.offset;
  139.   }
  140.   reference operator[](difference_type i) { return *(*this + i); }
  141.   bool operator==(const iterator& x) const {
  142.     return p == x.p && offset == x.offset;
  143.   }
  144.   bool operator!=(const iterator& x) const {
  145.     return p != x.p || offset != x.offset;
  146.   }
  147.   bool operator<(iterator x) const {
  148.     return p < x.p || (p == x.p && offset < x.offset);
  149.   }
  150. };
  151.  
  152. struct __bit_const_iterator
  153.   : public random_access_iterator<bool, ptrdiff_t>
  154. {
  155.   typedef bool                 reference;
  156.   typedef bool                 const_reference;
  157.   typedef const bool*          pointer;
  158.   typedef __bit_const_iterator const_iterator;
  159.  
  160.   unsigned int* p;
  161.   unsigned int offset;
  162.   void bump_up() {
  163.     if (offset++ == __WORD_BIT - 1) {
  164.       offset = 0;
  165.       ++p;
  166.     }
  167.   }
  168.   void bump_down() {
  169.     if (offset-- == 0) {
  170.       offset = __WORD_BIT - 1;
  171.       --p;
  172.     }
  173.   }
  174.  
  175.   __bit_const_iterator() : p(0), offset(0) {}
  176.   __bit_const_iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
  177.   __bit_const_iterator(const __bit_iterator& x) : p(x.p), offset(x.offset) {}
  178.   const_reference operator*() const {
  179.     return __bit_reference(p, 1U << offset);
  180.   }
  181.   const_iterator& operator++() {
  182.     bump_up();
  183.     return *this;
  184.   }
  185.   const_iterator operator++(int) {
  186.     const_iterator tmp = *this;
  187.     bump_up();
  188.     return tmp;
  189.   }
  190.   const_iterator& operator--() {
  191.     bump_down();
  192.     return *this;
  193.   }
  194.   const_iterator operator--(int) {
  195.     const_iterator tmp = *this;
  196.     bump_down();
  197.     return tmp;
  198.   }
  199.   const_iterator& operator+=(difference_type i) {
  200.     difference_type n = i + offset;
  201.     p += n / __WORD_BIT;
  202.     n = n % __WORD_BIT;
  203.     if (n < 0) {
  204.       offset = (unsigned int) n + __WORD_BIT;
  205.       --p;
  206.     } else
  207.       offset = (unsigned int) n;
  208.     return *this;
  209.   }
  210.   const_iterator& operator-=(difference_type i) {
  211.     *this += -i;
  212.     return *this;
  213.   }
  214.   const_iterator operator+(difference_type i) const {
  215.     const_iterator tmp = *this;
  216.     return tmp += i;
  217.   }
  218.   const_iterator operator-(difference_type i) const {
  219.     const_iterator tmp = *this;
  220.     return tmp -= i;
  221.   }
  222.   difference_type operator-(const_iterator x) const {
  223.     return __WORD_BIT * (p - x.p) + offset - x.offset;
  224.   }
  225.   const_reference operator[](difference_type i) { 
  226.     return *(*this + i); 
  227.   }
  228.   bool operator==(const const_iterator& x) const {
  229.     return p == x.p && offset == x.offset;
  230.   }
  231.   bool operator!=(const const_iterator& x) const {
  232.     return p != x.p || offset != x.offset;
  233.   }
  234.   bool operator<(const_iterator x) const {
  235.     return p < x.p || (p == x.p && offset < x.offset);
  236.   }
  237. };
  238.  
  239. // The next few lines are confusing.  What we're doing is declaring a
  240. //  partial specialization of vector<T, Alloc> if we have the necessary
  241. //  compiler support.  Otherwise, we define a class bit_vector which uses
  242. //  the default allocator.  In either case, we typedef "data_allocator" 
  243. //  appropriately.
  244.  
  245. #if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NEED_BOOL)
  246. #define __SGI_STL_VECBOOL_TEMPLATE
  247. #define __BVECTOR vector
  248. #else
  249. #undef __SGI_STL_VECBOOL_TEMPLATE
  250. #define __BVECTOR bit_vector
  251. #endif
  252.  
  253. #      ifdef __SGI_STL_VECBOOL_TEMPLATE
  254.        __STL_END_NAMESPACE
  255. #      include <stl_vector.h>
  256.        __STL_BEGIN_NAMESPACE
  257. template<class Alloc> class vector<bool, Alloc>
  258. #      else /* __SGI_STL_VECBOOL_TEMPLATE */
  259. class bit_vector
  260. #      endif /* __SGI_STL_VECBOOL_TEMPLATE */
  261. {
  262. #      ifdef __SGI_STL_VECBOOL_TEMPLATE
  263.   typedef simple_alloc<unsigned int, Alloc> data_allocator;
  264. #      else /* __SGI_STL_VECBOOL_TEMPLATE */
  265.   typedef simple_alloc<unsigned int, alloc> data_allocator;  
  266. #      endif /* __SGI_STL_VECBOOL_TEMPLATE */
  267. public:
  268.   typedef bool value_type;
  269.   typedef size_t size_type;
  270.   typedef ptrdiff_t difference_type; 
  271.   typedef __bit_reference reference;
  272.   typedef bool const_reference;
  273.   typedef __bit_reference* pointer;
  274.   typedef const bool* const_pointer;
  275.  
  276.   typedef __bit_iterator                iterator;
  277.   typedef __bit_const_iterator          const_iterator;
  278.  
  279. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  280.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  281.   typedef reverse_iterator<iterator> reverse_iterator;
  282. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  283.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  284.                            difference_type> const_reverse_iterator;
  285.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  286.           reverse_iterator;
  287. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  288.  
  289. protected:
  290.   iterator start;
  291.   iterator finish;
  292.   unsigned int* end_of_storage;
  293.   unsigned int* bit_alloc(size_type n) {
  294.     return data_allocator::allocate((n + __WORD_BIT - 1)/__WORD_BIT);
  295.   }
  296.   void deallocate() {
  297.     if (start.p)
  298.       data_allocator::deallocate(start.p, end_of_storage - start.p);
  299.   }
  300.   void initialize(size_type n) {
  301.     unsigned int* q = bit_alloc(n);
  302.     end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
  303.     start = iterator(q, 0);
  304.     finish = start + difference_type(n);
  305.   }
  306.   void insert_aux(iterator position, bool x) {
  307.     if (finish.p != end_of_storage) {
  308.       copy_backward(position, finish, finish + 1);
  309.       *position = x;
  310.       ++finish;
  311.     }
  312.     else {
  313.       size_type len = size() ? 2 * size() : __WORD_BIT;
  314.       unsigned int* q = bit_alloc(len);
  315.       iterator i = copy(begin(), position, iterator(q, 0));
  316.       *i++ = x;
  317.       finish = copy(position, end(), i);
  318.       deallocate();
  319.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  320.       start = iterator(q, 0);
  321.     }
  322.   }
  323.  
  324. #ifdef __STL_MEMBER_TEMPLATES
  325.   template <class InputIterator>
  326.   void initialize_range(InputIterator first, InputIterator last,
  327.                         input_iterator_tag) {
  328.     start = iterator();
  329.     finish = iterator();
  330.     end_of_storage = 0;
  331.     for ( ; first != last; ++first) 
  332.       push_back(*first);
  333.   }
  334.  
  335.   template <class ForwardIterator>
  336.   void initialize_range(ForwardIterator first, ForwardIterator last,
  337.                         forward_iterator_tag) {
  338.     size_type n = 0;
  339.     distance(first, last, n);
  340.     initialize(n);
  341.     copy(first, last, start);
  342.   }
  343.  
  344.   template <class InputIterator>
  345.   void insert_range(iterator pos,
  346.                     InputIterator first, InputIterator last,
  347.                     input_iterator_tag) {
  348.     for ( ; first != last; ++first) {
  349.       pos = insert(pos, *first);
  350.       ++pos;
  351.     }
  352.   }
  353.  
  354.   template <class ForwardIterator>
  355.   void insert_range(iterator position,
  356.                     ForwardIterator first, ForwardIterator last,
  357.                     forward_iterator_tag) {
  358.     if (first != last) {
  359.       size_type n = 0;
  360.       distance(first, last, n);
  361.       if (capacity() - size() >= n) {
  362.         copy_backward(position, end(), finish + difference_type(n));
  363.         copy(first, last, position);
  364.         finish += difference_type(n);
  365.       }
  366.       else {
  367.         size_type len = size() + max(size(), n);
  368.         unsigned int* q = bit_alloc(len);
  369.         iterator i = copy(begin(), position, iterator(q, 0));
  370.         i = copy(first, last, i);
  371.         finish = copy(position, end(), i);
  372.         deallocate();
  373.         end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  374.         start = iterator(q, 0);
  375.       }
  376.     }
  377.   }      
  378.  
  379. #endif /* __STL_MEMBER_TEMPLATES */
  380.  
  381. public:
  382.   iterator begin() { return start; }
  383.   const_iterator begin() const { return start; }
  384.   iterator end() { return finish; }
  385.   const_iterator end() const { return finish; }
  386.  
  387.   reverse_iterator rbegin() { return reverse_iterator(end()); }
  388.   const_reverse_iterator rbegin() const { 
  389.     return const_reverse_iterator(end()); 
  390.   }
  391.   reverse_iterator rend() { return reverse_iterator(begin()); }
  392.   const_reverse_iterator rend() const { 
  393.     return const_reverse_iterator(begin()); 
  394.   }
  395.  
  396.   size_type size() const { return size_type(end() - begin()); }
  397.   size_type max_size() const { return size_type(-1); }
  398.   size_type capacity() const {
  399.     return size_type(const_iterator(end_of_storage, 0) - begin());
  400.   }
  401.   bool empty() const { return begin() == end(); }
  402.   reference operator[](size_type n) {
  403.     return *(begin() + difference_type(n));
  404.   }
  405.   const_reference operator[](size_type n) const {
  406.     return *(begin() + difference_type(n));
  407.   }
  408.   __BVECTOR() : start(iterator()), finish(iterator()), end_of_storage(0) {}
  409.   __BVECTOR(size_type n, bool value) {
  410.     initialize(n);
  411.     fill(start.p, end_of_storage, value ? ~0 : 0);
  412.   }
  413.   __BVECTOR(int n, bool value) {
  414.     initialize(n);
  415.     fill(start.p, end_of_storage, value ? ~0 : 0);
  416.   }
  417.   __BVECTOR(long n, bool value) {
  418.     initialize(n);
  419.     fill(start.p, end_of_storage, value ? ~0 : 0);
  420.   }
  421.   explicit __BVECTOR(size_type n) {
  422.     initialize(n);
  423.     fill(start.p, end_of_storage, 0);
  424.   }
  425.   __BVECTOR(const __BVECTOR& x) {
  426.     initialize(x.size());
  427.     copy(x.begin(), x.end(), start);
  428.   }
  429.  
  430. #ifdef __STL_MEMBER_TEMPLATES
  431.   template <class InputIterator>
  432.   __BVECTOR(InputIterator first, InputIterator last) {
  433.     initialize_range(first, last, iterator_category(first));
  434.   }
  435. #else /* __STL_MEMBER_TEMPLATES */
  436.   __BVECTOR(const_iterator first, const_iterator last) {
  437.     size_type n = 0;
  438.     distance(first, last, n);
  439.     initialize(n);
  440.     copy(first, last, start);
  441.   }
  442.   __BVECTOR(const bool* first, const bool* last) {
  443.     size_type n = 0;
  444.     distance(first, last, n);
  445.     initialize(n);
  446.     copy(first, last, start);
  447.   }
  448. #endif /* __STL_MEMBER_TEMPLATES */
  449.  
  450.   ~__BVECTOR() { deallocate(); }
  451.   __BVECTOR& operator=(const __BVECTOR& x) {
  452.     if (&x == this) return *this;
  453.     if (x.size() > capacity()) {
  454.       deallocate();
  455.       initialize(x.size());
  456.     }
  457.     copy(x.begin(), x.end(), begin());
  458.     finish = begin() + difference_type(x.size());
  459.     return *this;
  460.   }
  461.   void reserve(size_type n) {
  462.     if (capacity() < n) {
  463.       unsigned int* q = bit_alloc(n);
  464.       finish = copy(begin(), end(), iterator(q, 0));
  465.       deallocate();
  466.       start = iterator(q, 0);
  467.       end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
  468.     }
  469.   }
  470.   reference front() { return *begin(); }
  471.   const_reference front() const { return *begin(); }
  472.   reference back() { return *(end() - 1); }
  473.   const_reference back() const { return *(end() - 1); }
  474.   void push_back(bool x) {
  475.     if (finish.p != end_of_storage)
  476.       *finish++ = x;
  477.     else
  478.       insert_aux(end(), x);
  479.   }
  480.   void swap(__BVECTOR& x) {
  481.     __STD::swap(start, x.start);
  482.     __STD::swap(finish, x.finish);
  483.     __STD::swap(end_of_storage, x.end_of_storage);
  484.   }
  485.   iterator insert(iterator position, bool x = bool()) {
  486.     difference_type n = position - begin();
  487.     if (finish.p != end_of_storage && position == end())
  488.       *finish++ = x;
  489.     else
  490.       insert_aux(position, x);
  491.     return begin() + n;
  492.   }
  493.  
  494. #ifdef __STL_MEMBER_TEMPLATES
  495.   template <class InputIterator> void insert(iterator position,
  496.                                              InputIterator first,
  497.                                              InputIterator last) {
  498.     insert_range(position, first, last, iterator_category(first));
  499.   }
  500. #else /* __STL_MEMBER_TEMPLATES */
  501.   void insert(iterator position, const_iterator first, 
  502.               const_iterator last) {
  503.     if (first == last) return;
  504.     size_type n = 0;
  505.     distance(first, last, n);
  506.     if (capacity() - size() >= n) {
  507.       copy_backward(position, end(), finish + n);
  508.       copy(first, last, position);
  509.       finish += n;
  510.     }
  511.     else {
  512.       size_type len = size() + max(size(), n);
  513.       unsigned int* q = bit_alloc(len);
  514.       iterator i = copy(begin(), position, iterator(q, 0));
  515.       i = copy(first, last, i);
  516.       finish = copy(position, end(), i);
  517.       deallocate();
  518.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  519.       start = iterator(q, 0);
  520.     }
  521.   }
  522.  
  523.   void insert(iterator position, const bool* first, const bool* last) {
  524.     if (first == last) return;
  525.     size_type n = 0;
  526.     distance(first, last, n);
  527.     if (capacity() - size() >= n) {
  528.       copy_backward(position, end(), finish + n);
  529.       copy(first, last, position);
  530.       finish += n;
  531.     }
  532.     else {
  533.       size_type len = size() + max(size(), n);
  534.       unsigned int* q = bit_alloc(len);
  535.       iterator i = copy(begin(), position, iterator(q, 0));
  536.       i = copy(first, last, i);
  537.       finish = copy(position, end(), i);
  538.       deallocate();
  539.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  540.       start = iterator(q, 0);
  541.     }
  542.   }
  543. #endif /* __STL_MEMBER_TEMPLATES */
  544.   
  545.   void insert(iterator position, size_type n, bool x) {
  546.     if (n == 0) return;
  547.     if (capacity() - size() >= n) {
  548.       copy_backward(position, end(), finish + difference_type(n));
  549.       fill(position, position + difference_type(n), x);
  550.       finish += difference_type(n);
  551.     }
  552.     else {
  553.       size_type len = size() + max(size(), n);
  554.       unsigned int* q = bit_alloc(len);
  555.       iterator i = copy(begin(), position, iterator(q, 0));
  556.       fill_n(i, n, x);
  557.       finish = copy(position, end(), i + difference_type(n));
  558.       deallocate();
  559.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  560.       start = iterator(q, 0);
  561.     }
  562.   }
  563.  
  564.   void insert(iterator pos, int n, bool x)  { insert(pos, (size_type)n, x); }
  565.   void insert(iterator pos, long n, bool x) { insert(pos, (size_type)n, x); }
  566.  
  567.   void pop_back() { --finish; }
  568.   iterator erase(iterator position) {
  569.     if (position + 1 != end())
  570.       copy(position + 1, end(), position);
  571.     --finish;
  572.     return position;
  573.   }
  574.   iterator erase(iterator first, iterator last) {
  575.     finish = copy(last, end(), first);
  576.     return first;
  577.   }
  578.   void resize(size_type new_size, bool x = bool()) {
  579.     if (new_size < size()) 
  580.       erase(begin() + difference_type(new_size), end());
  581.     else
  582.       insert(end(), new_size - size(), x);
  583.   }
  584.   void clear() { erase(begin(), end()); }
  585. };
  586.  
  587. #ifdef __SGI_STL_VECBOOL_TEMPLATE
  588.  
  589. typedef vector<bool, alloc> bit_vector;
  590.  
  591. #else /* __SGI_STL_VECBOOL_TEMPLATE */
  592.  
  593. inline bool operator==(const bit_vector& x, const bit_vector& y) {
  594.   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  595. }
  596.  
  597. inline bool operator<(const bit_vector& x, const bit_vector& y) {
  598.   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  599. }
  600.  
  601. #endif /* __SGI_STL_VECBOOL_TEMPLATE */
  602.  
  603. #undef __SGI_STL_VECBOOL_TEMPLATE
  604. #undef __BVECTOR
  605.  
  606. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  607. #pragma reset woff 1174
  608. #endif
  609.  
  610. __STL_END_NAMESPACE 
  611.  
  612. #endif /* __SGI_STL_INTERNAL_BVECTOR_H */
  613.  
  614. // Local Variables:
  615. // mode:C++
  616. // End:
  617.